{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 9 10 13 "
     ]
    }
   ],
   "source": [
    "#include<stdio.h>\n",
    "#include<stdlib.h>\n",
    "\n",
    "\n",
    "void swap(int tree[],int i,int j){\n",
    "    int tmp = tree[i];\n",
    "    tree[i] = tree[j];\n",
    "    tree[j] = tmp;\n",
    "}\n",
    "\n",
    "//调整堆\n",
    "void heapify(int tree[],int n,int i){\n",
    "    if(i >= n){\n",
    "        return;\n",
    "    }\n",
    "    int c1 = 2*i + 1;\n",
    "    int c2 = 2*i + 2;\n",
    "    int max = i;\n",
    "    if(c1 < n && tree[c1] > tree[max]){\n",
    "        max = c1;\n",
    "    }\n",
    "    if(c2 < n && tree[c2] > tree[max]){\n",
    "        max = c2;\n",
    "    }\n",
    "    if(max != i){\n",
    "        swap(tree,i,max);\n",
    "        heapify(tree,n,max);\n",
    "    }\n",
    "}\n",
    "\n",
    "//创建堆\n",
    "//从h-1层的最左边的节点开始调整\n",
    "void build_heap(int tree[],int n){\n",
    "    int last_node = n - 1;\n",
    "    int parent = (last_node - 1)/ 2 ;\n",
    "    for(int i=parent;i >=0;i--){\n",
    "        heapify(tree,n,i);\n",
    "    }\n",
    "}\n",
    "\n",
    "//堆排序，升序\n",
    "void heap_sort(int tree[],int n){\n",
    "    build_heap(tree,n);\n",
    "    for(int i=n-1;i>=0;i--){\n",
    "        //最后一个与根节点进行交换\n",
    "        swap(tree,i,0);\n",
    "        //调整根节点，注意此时的第二个参数也就是处理的数组大小变成了i哦，相当于斩断了最后一个节点\n",
    "        heapify(tree,i,0);\n",
    "    }\n",
    "}\n",
    "\n",
    "int main(){\n",
    "    int tree[] = {4,10,3,5,1,2,9,6,13};\n",
    "    int n = 9;\n",
    "    heap_sort(tree,n);\n",
    "    for(int i=0;i<n;i++){\n",
    "        printf(\"%d \",tree[i]);\n",
    "    }\n",
    "    return 0;\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
